There are known technologies for parallelizing a program, which is for a sequential computer (hereinafter referred to as a sequential program), so that the program can be processed in parallel by a plurality of cores or processors. In the parallelization of a sequential program, a loop in the program that occupies much time of computation time is typically parallelized. There have conventionally been various techniques developed for parallelization of loops, but there still are some loops that are difficult to parallelize. One example of such loops which are difficult to parallelize is a loop whose number of iterations is not known before being executed.
In a conventional technology for parallelizing a program including a loop whose number of iterations is not known before being executed, data values to be used after termination of the loop are ensured using a technique called rollback to perform parallelization. According to this technology, data values are ensured by saving data to be used after termination of the loop at execution of each thread and restoring the saved data when the loop is terminated. Thus, a situation can be avoided in which the result of executing a parallelized version of a sequential program is different from the result of executing the sequential program.
For rollback, however, it is necessary to reserve a memory area for saving the data to be used after termination of the loop, and this waste the memory capacity. In addition, according to a conventional rollback technology, operations such as saving necessary data, detecting loop termination, notifying other threads, reading out an appropriate value from saved data and replacing data is required. As a result, complex control is required.